package algorithm;

import java.util.Arrays;
import java.util.Random;

public class QuickSort<T extends Comparable<T>> {
	private static int with = 30;
	private static int length = 600;
	private static Random random = new Random();
	
	QuickSort() {
	}

	QuickSort(int with, int length) {
		QuickSort.with = with;
		QuickSort.length = length;
	}
	
	public static void main(String[] args) {
		Integer[] array = new Integer[length];
		
		for (int i = 0; i < length; i++) {
			array[i] = random.nextInt(900) + 100;
		}
		QuickSort<Integer> qs = new QuickSort<Integer>();
		Integer[] randomArr = Arrays.copyOf(array, length);
		//print the unsorted array
		qs.print(array);
		
		//count the nanosecond of common quick sort
		long start = System.nanoTime();		
		qs.commonQuickSort(array);
		long end = System.nanoTime();
		
		System.out.println("\nThe common quick sort spend " + (end - start) + " nanosecend and the result is:\n");
		qs.print(array);
		
		//count the nanosecond of random quick sort
		start = System.nanoTime();
		qs.randomQuickSort(randomArr);
		end = System.nanoTime();
		
		System.out.println("\nThe random quick sort spend " + (end - start) + " nanosecend and the result is:\n");
		qs.print(randomArr);
		
	}
	
	/*
	 * according to common quick sort algorithm, sort the array
	 */
	private void commonQuickSort(T[] array) {
		commonQuickSort(array, 0, array.length - 1);
	}
	
	/*
	 * according to random quick sort algorithm, sort the array
	 */
	private void randomQuickSort(T[] array) {
		randomQuickSort(array, 0, array.length - 1);
	}
	
	/*
	 * according to common quick sort algorithm, sort the array specified by given indices.
	 */
	private void commonQuickSort(T[] array, int p, int r) {
		if (p < r) {
			int q = commonPartition(array, p, r);
			commonQuickSort(array, p, q - 1);
			commonQuickSort(array, q + 1, r);
		}
	}
	
	/*
	 * according to random quick sort algorithm, sort the array specified by given indices.
	 */
	private void randomQuickSort(T[] array, int p, int r) {
		if (p < r) {
			int q = randomPartition(array, p, r);
			randomQuickSort(array, p, q - 1);
			randomQuickSort(array, q + 1, r);
		}
	}
	
	/*
	 * partition the array by key element, the last element as key element, return the final index of key element
	 */
	private int commonPartition(T[] array, int p, int r) {
		T x = array[r];
		int i = p -1;
		int compare;
		for(int j = p; j < r; j++) {
			compare = array[j].compareTo(x);
			if (compare <= 0) {
				i++;
				swap(array, i, j);
			}
		}
		swap(array, i + 1, r);
		return i + 1;
	}
	
	/*
	 * partition the array by key element, the random element as key element, return the final index of key element
	 */
	private int randomPartition(T[] array, int p, int r) {
		int k = random.nextInt(r - p + 1) + p;
		swap (array, r, k);
		T x = array[r];
		int i = p -1;
		int compare;
		for(int j = p; j < r; j++) {
			compare = array[j].compareTo(x);
			if (compare <= 0) {
				i++;
				swap(array, i, j);
			}
		}
		swap(array, i + 1, r);
		return i + 1; 
	}
	
	/*
	 * swap the nodes specified by given indices, if the indices are equal, do nothing
	 */
	private  static void swap(Object[] array, int p, int q) {
		if (p == q) {
			return;
		}
		Object temp = array[p];
		array[p] = array[q];
		array[q] = temp;
	}
	
	private void print(Object[] array) {
		int i = 1;
		for(Object o : array) {
			System.out.print(o);
			System.out.print(' ');
			if(i++ % with == 0) {
				System.out.println();
			}
		}
	}
}
